package com.topcoder.srm236;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class Parking {
	private int 		INF = 2501;
	private ArrayList<Point> cars;
	private ArrayList<Point> lots;
	private int 		X;
	private int 		Y;
	private int 		C;
	private int 		P;
	private int[][] 	dist;
	private String[] 	park;
	private int			matched;
	
	public int minTime(String[] park) {
		this.park = park;
		cars = new ArrayList<Point>();
		lots = new ArrayList<Point>();
		X = park.length;
		Y = park[0].length();
		
		for (int x=0; x<X; x++) {
			for (int y=0; y<Y; y++) {
				if (park[x].charAt(y) == 'C') {
					cars.add(new Point(x, y));
				}
				else if (park[x].charAt(y) == 'P') {
					lots.add(new Point(x, y));
				}
			}
		}
		
		C = cars.size();
		P = lots.size();
		if (C > P) return -1;
		if (C == 0) return 0;
		dist = new int[C][P];
		for (int i=0; i<C; i++) {
			int[][] d = minDist(cars.get(i));
			for (int j=0; j<P; j++) {
				dist[i][j] = d[lots.get(j).x][lots.get(j).y];
			}
		}
		
		int[] c = new int[C];
		for (int i=0; i<C; i++) c[i] = -1;
		int[] p = new int[P];
		for (int i=0; i<P; i++) p[i] = -1;
		
		int min = -1;
		ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
		while (matched < C) {
			min = nextMin(min);
			if (min == INF) return -1;
			for (int i=0; i<C; i++) {
				if (c[i] >= 0) continue;
				findAugment(min, c, p, dq, i);
			}
		}
		
		return min;
	}
	
	private void findAugment(int min, int[] c, int[] p, ArrayDeque<Integer> dq, int source) {
		dq.clear();
		dq.add(source);
		
		int[] from = new int[C];
		for (int i=0; i<C; i++) from[i] = -1;
		from[source] = source;
			
		while (!dq.isEmpty()) {
			int current = dq.remove();
			for (int j=0; j<P; j++) {
				if (dist[current][j] > min) continue;
				
				if (p[j] < 0) {
					while (from[current] != current) {
						int aux = c[current];
						c[current] = j;
						p[j] = current;
						current = from[current];
						j = aux;
					}
					c[current] = j;
					p[j] = current;
					matched++;
					return;
				}
				else {
					if (from[p[j]] < 0) {
						dq.add(p[j]);
						from[p[j]] = current;
					}
				}
			}
		}
	}
	
	private int nextMin(int min) {
		int next = INF;
		for (int i=0; i<C; i++) {
			for (int j=0; j<P; j++) {
				if (dist[i][j] > min && dist[i][j] < next) next = dist[i][j];
			}
		}
		return next;
	}
	
	private int[][] minDist(Point c) {
		int[][] d = new int[X][Y];
		for (int i=0; i<X; i++) {
			for (int j=0; j<Y; j++) {
				d[i][j] = INF;
			}
		}
		
		ArrayDeque<Point> queue = new ArrayDeque<Point>();
		queue.add(c);
		d[c.x][c.y] = 0;
		
		while(!queue.isEmpty()) {
			Point p = queue.remove();
			int value = d[p.x][p.y] + 1;
			addPoint(p.x-1, p.y, queue, d, value);
			addPoint(p.x+1, p.y, queue, d, value);
			addPoint(p.x, p.y-1, queue, d, value);
			addPoint(p.x, p.y+1, queue, d, value);
		}
		
		return d;
	}
	
	private void addPoint(int x, int y, ArrayDeque<Point> queue, int[][] d, int value) {
		if (x < 0 || x >= X || y < 0 || y >= Y 
				|| park[x].charAt(y) == 'X' || value >= d[x][y]) return;
		d[x][y] = value;
		queue.add(new Point(x, y));
	}
	
	private class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}
